#include <iostream>
#include <random>
#include <vector>

void merge(std::vector<int>& arr,int startPos,int midPos,int endPos)
{
    std::vector<int> tempArr={};
    tempArr.resize(endPos-startPos+1);
    int p1=startPos;
    int p2=midPos+1;
    int p=0;
    while(p1<=midPos && p2<=endPos)
    {
        if(arr.at(p1)<=arr.at(p2))
            tempArr.at(p++)=arr.at(p1++);
        else
            tempArr.at(p++)=arr.at(p2++);
    }
    while (p1<=midPos)
        tempArr.at(p++)=arr.at(p1++);
    while (p2<=endPos)
        tempArr.at(p++)=arr.at(p2++);
    for(int i=0;i<tempArr.size();i++)
        arr.at(i+startPos)=tempArr.at(i);
}

void mergeSort(std::vector<int>& arr,int startPos,int endPos)
{
    if(startPos<endPos)
    {
        int mid=(startPos+endPos)/2;
        mergeSort(arr,startPos,mid);
        mergeSort(arr,mid+1,endPos);
        merge(arr,startPos,mid,endPos);
    }
}

int main()
{
    std::default_random_engine randomE;
    std::uniform_int_distribution<int> randomInt(1,1000);
    std::vector<int> arr;
    arr.resize(50);
    for(int& i:arr)
        i=randomInt(randomE);
    mergeSort(arr,0,arr.size()-1);
    for(int i:arr)
        std::cout<<i<<' ';
    std::cout<<std::endl;
    return 0;
}